Multiprotocol Label Switching (“MPLS”) provides a mechanism for engineering network traffic patterns that is independent of routing tables. MPLS assigns short labels to network packets that describe how to forward them through the network. MPLS is independent of any routing protocol. In a MPLS network, a node, switch or router which supports MPLS is generally known as a label switching router (“LSR”) and a LSR at the edge (ingress or egress) of the MPLS network is generally known as a label edge router (“LER”).
Now, as a data frame of a connectionless network layer protocol (e.g., the Internet Protocol (“IP”)) travels from a source node to a destination node it travels from one node to the next through the network. Each node makes an independent forwarding decision for that packet. That is, each node analyzes the data frame's header to determine where to forward the packet next. The forwarding decision is determined by a forwarding table that is present on each node and that is built by network layer routing algorithms running on that node. Therefore each router independently chooses a next hop for the data frame, based on its analysis of the packet's header and the results of running the routing algorithm.
Frame headers contain considerably more information than is needed simply to choose the next hop along the path. Choosing the next hop can therefore be thought of as the composition of two functions. The first function partitions the entire set of possible packets into a set of forwarding equivalence classes (“FECs”). In conventional IP forwarding the FEC is a subnet IP address prefix. Therefore a particular node will typically consider two packets to be in the same FEC if there is some address prefix “X” in that router's routing tables such that “X” is the “longest match” for each packet's destination address. The second maps each FEC to a next hop. Insofar as the forwarding decision is concerned, different packets which get mapped into the same FEC are indistinguishable. All data frames which belong to a particular FEC and which travel from a particular node will follow the same path (or if certain kinds of multi-path routing are in use, they will all follow one of a set of paths associated with the FEC). As the data frame traverses the network, each hop in turn re-examines the packet and matches it to a FEC in order to determine the next-hop.
In MPLS, the assignment of a particular data frame to a particular FEC is done just once, as the data frame enters the network. The FEC to which the packet is assigned is encoded as a short fixed length value known as a “label”. When a packet is forwarded to its next hop, the label is sent along with it; that is, the packets are “labelled” before they are forwarded. At subsequent hops, there is no further analysis of the data frame's network layer header. Rather, the label in the frame header is used as an index into a table on the node. The table entry specifies the next hop, and a new label. The old label in the frame header is replaced with the new label, and the data frame is forwarded to its next hop. Thus, in the MPLS forwarding paradigm, once a packet is assigned to a FEC, no further network layer header analysis is done by subsequent routers; all forwarding is driven by the labels.
For reference, the MPLS header is made up of a stack of 32 bit labels. The MPLS “label” is 20 bits long and is the identifier that is locally significant to the LSR. The “experimental bits” field is 3 bits long and is used to determine the quality of service (“QoS”) that is to be applied to the data frame. The “stack” field takes one bit and is used to determine whether there is another label stack entry in the header. And, the time-to-live (“TTL”) field is 8 bits long and is similar to the TTL field carried in the IP header and is used to determine how many hops the frame can traverse before it is dropped. The IP frame is encapsulated in with an MPLS header at the ingress edge of the MPLS network. At the egress edge, the IP frame is restored by removing the MPLS header.
Label switched paths (“LSPs”) are specific traffic paths though an MPLS network. They are similar to circuit switched paths such as those found in ATM or Frame Relay networks and their use can guarantee a specific level of performance. Packets are forwarded along a LSP where each LSR makes forwarding decisions based solely on the contents of the label. MPLS enables routers to make forwarding decisions based on the contents of the shortened MPLS label, rather than by performing a complex route lookup based on the destination network layer address.
Now, a provider that offers IP connectivity using a common MPLS backbone network sells services to hundreds of customers. Each customer at any given time has a known bandwidth requirement. Each physical link in the provider's backbone has a fixed bandwidth. Providing bandwidth over some links may be more expensive than over others (in the case where a provider leases bandwidth from another provider), or uses a more expensive media to provide connectivity. There are certain links that charge based on the minute (even if there is no traffic on this link at a given time) or by the mile, as opposed to other links that charge by the packet. As well, each link may have a different latency and reliability.
For each customer that requires connectivity between a pair of sites, a cost is incurred. This cost depends on the medium used to provide the service and the distance between the sites. As well, traffic that travels between these two sites incurs a latency and has a certain reliability. The latency is determined by the media used to provide the service, the number of hops between the sites, and the amount of time it takes for the data to be processed at each node along the path. Operators wish to arrange a minimum cost bandwidth usage pattern. For lower paying customers, operators may provide a service that maximizes the usage of the resources in the network while attempting to keep costs as low as possible with no latency and reliability guarantees. On the other hand, for higher paying customers, operators may provide a service with smaller latency and higher reliability at the least cost possible. Maximum flow and minimum cost problem algorithms are applied to MPLS networks to allow operators to offer higher paying customers guaranteed bandwidth, low latency and high reliability services.
Conventional IP systems use Interior Gateway Protocols (“IGPs”) such as Intermediate System-Intermediate System (“IS-IS”) and Open Shortest Path First (“OSPF”). Exterior Gateway Protocols (“EGPs”) such as Border Gateway Protocol (“BGP”) and Asynchronous Transfer Mode (“ATM”) systems use the Private Network-Network Interface (“PNNI”) to make independent routing decisions using a local instantiation of a synchronized routing area link state database. Route selection is typically based on shortest path computations using simple additive link metrics. One problem with these routing protocols is that they only consider the shortest path but do not consider the characteristics of the data traffic and network link latency and capacity constraints when making routing decisions. This results in some links of the network becoming congested, while other links along alternate paths remain underutilized. This also leads to the underutilization of network resources. In addition, data originating from sites of higher paying customers may not be treated any differently from data originating from other customer sites.
Thus, depending on what links are selected in the network when MPLS LSPs are provisioned, the network usage may not be optimal. This may result in prevention of provisioning of newer LSPs even though network capacity exists. One way to solve this problem is for the operator of the network to study the network and determine ways to reassign or move LSPs. Moving an LSP typically requires the complete tear down of the existing LSPs, creation of new LSPs, and recreation of previous LSPs using the selected routes through the network determined by the operator. However, this is time consuming and there is no guarantee that the operator will choose an optimal update for the network. Moreover, this task is difficult to perform for a network with a large number of LSPs.
A need therefore exists for an improved method and system for maximizing network capacity unitization in MPLS networks by moving LSPs in the network. Accordingly, a solution that addresses, at least in part, the above and other shortcomings is desired.